import java.util.Arrays;

public class KLargest {

	public static void main(String[] args) {
		KLargest kl = new KLargest();
		int[] arr = new int[] { 3, 2, 5, 4, 1, 6, 1, 6 };
		//System.out.println(kl.kLargest(arr, 4));
		System.out.println(kl.ksmallest(arr, 3));

		int[] arr1 = new int[] { 1, 3, 5, 7, 9 };
		int[] arr2 = new int[] { 2, 4, 5, 5, 6, 8, 10 };
		//System.out.println(kl.kLargest2(arr1, arr2, 3));
	}

	public int kLargest2(int[] arr1, int[] arr2, int k) {
		if ((arr1 == null && arr2 == null) || arr1.length + arr2.length < k)
			throw new RuntimeException("Invalid input");

		Arrays.sort(arr1);
		Arrays.sort(arr2);

		int p1 = arr1.length - 1, p2 = arr2.length - 1;
		int r1 = arr1.length - p1 - 1, r2 = arr2.length - p2 - 1;
		while (p1 >= 0 && p2 >= 0 && r1 + r2 < k) {
			if (r1 + r2 == k - 1) {
				if (arr1[p1] <= arr2[p2])
					return arr2[p2];
				else
					return arr1[p1];
			} else {
				if (arr1[p1] < arr2[p2]) {
					--p2;
					r2 = arr2.length - p2 - 1;
				} else {
					--p1;
					r1 = arr1.length - p1 - 1;
				}
			}
		}

		if (p1 < 0)
			return arr2[arr2.length - (k - arr1.length)];
		else
			return arr1[arr1.length - (k - arr2.length)];
	}

	public int kLargest(int[] arr, int k) {
		if (arr == null || arr.length < k)
			throw new RuntimeException("Invalid array.");

		return kLargestRecursion(arr, 0, arr.length - 1, k);
	}

	private int kLargestRecursion(int[] arr, int left, int right, int k) {
		// Select pivot
		int pivotIndex = (int) (Math.random() * (right - left + 1) + left);
		int pivot = arr[pivotIndex];

		// Do partition
		int swapIndex = left;
		swap(arr, pivotIndex, right);
		for (int i = left; i < right; ++i) {
			if (arr[i] <= pivot) {
				swap(arr, i, swapIndex);
				++swapIndex;
			}
		}
		swap(arr, swapIndex, right);

		// rank-th element of pivot
		int rank = right - swapIndex + 1;
		if (rank == k)
			return arr[swapIndex];
		else if (rank > k)
			return kLargestRecursion(arr, swapIndex + 1, right, k);
		else
			return kLargestRecursion(arr, left, swapIndex - 1, k - rank);
	}

	private void swap(int[] arr, int i, int j) {
		if (i != j) {
			arr[i] ^= arr[j];
			arr[j] ^= arr[i];
			arr[i] ^= arr[j];
		}
	}

	int ksmallest(int [] arr, int k){
		return ksmallest2(arr, 0, arr.length-1, k);
	}

	int ksmallest2(int [] arr, int h, int t, int k){
		int pidx = (int)(Math.random()*(t-h+1) + h);
		int pivot =arr[pidx];

		int sidx = h;
		swap(arr, pidx, t);
		for (int i=h; i< t; ++i){
			if (arr[i] <= pivot){
				swap(arr, i, sidx);
				++sidx;
			}
		}
		// swap
		swap(arr, sidx, t);

		if (sidx-h == k-1)
			return arr[sidx];
		else if (sidx-h > k-1)
			return ksmallest2(arr, h, sidx-1, k);
		else
			return ksmallest2(arr, sidx+1, t, k-sidx-1);
			
	}
}
